/**
 * 给定一个单链表的头节点 head，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。
 *
 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差不超过 1。
 *
 *
 *https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/
 */
class SortedListToBST {
    public TreeNode sortedListToBST(ListNode head) {
        return sortedListToBST(head,null);
    }
    public TreeNode sortedListToBST(ListNode head,ListNode tail){
        if(head==tail){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=tail&&fast.next!=tail){
            slow=slow.next;
            fast=fast.next.next;
        }
        TreeNode root=new TreeNode(slow.val);
        root.left=sortedListToBST(head,slow);
        root.right=sortedListToBST(slow.next,tail);
        return root;
    }
}